package sort;


import java.util.Scanner;

/*
* 实现归并排序
* */
public class P_M{
    public static void main(String[] args) {
        int[] arr={1,3,2,5,4,6,9,8,7};
        pmSort(arr);
        for (int x:arr){
            System.out.println(x);
        }
    }

    /*
    * 归并排序的方法
    * */
    public static void pmSort(int[] arr){
        if (arr==null || arr.length<=1){
            return;
        }
        process(arr,0,arr.length-1);
    }

    /*
    * 把arr[L-R] 上排好序
    * */
    public static void process(int[] arr,int left,int right){
        if (left == right){
            return;
        }
        int mid = left + ((right-left)>>1);   //划分新的中间点
        process(arr,left,mid);
        process(arr,mid+1,right);
        merge(arr,left,mid,right);   //让left - mid - right之间有序
    }
    //
    public static void merge(int[] arr,int left,int mid,int right){
        int[] help=new int[right - left +1];    //创建一个新的数组
        int i=0;
        int p1=left;
        int p2=mid+1;
        while (p1<=mid  && p2<=right){
            help[i++] = arr[p1] <=arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1<=mid){
            help[i++] = arr[p1++];
        }
        while (p2<=right){
            help[i++] = arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[left+i] = help[i];
        }
    }

}
